/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package edu.gmu.javalution.crowd;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;

/**
 *
 * @author jason.handuber
 */
public class Crowd<VEC>
{

    private final Map<VEC, Double> vecs2CD =
                                   new HashMap<VEC, Double>();
    private final int vectorLength;
    private final IProvideDistance<VEC> distance;
    private final IIndexComparator<VEC> indexComparator;
    private final INormalize<VEC> normalizer;
    private boolean dirty = false;

    /**
     * Creates a {@code Crowd} object that calculates the crowding distance
     * around a given set of {@code VEC}. These {@code VEC}s are provided using
     * the {@code increment} method. Note: this constructor DOES NOT provide
     * normalization of the values in each vector, which tends to make the
     * crowding metric less meaningful. Use the other constructor to include
     * a on-the-fly normalization.
     * @param vectorLength the length of the vectors, this is the number
     * of indices contained in each vector. all vectors must have the
     * same number of indices.
     * @param distance a function that provides the distance between two
     * vectors, recommended that distance returned is normalized
     * @param indexComparator a radiix sorter by vector index
     */
    public Crowd(int vectorLength, IProvideDistance<VEC> distance,
            IIndexComparator<VEC> indexComparator)
    {
        this(vectorLength, distance, indexComparator, null);
    }

    /**
     * Creates a {@code Crowd} object that calculates the crowding distance
     * around a given set of {@code VEC}. These {@code VEC}s are provided using
     * the {@code increment} method. This constructor DOES provide
     * normalization of the values in each vector, which tends to make the
     * crowding metric more meaningful. Use the other constructor if the
     * vector values are already normalized or are at least "close" to
     * eachother in values (e.g. all values between 0 and 1).
     * @param vectorLength the length of the vectors, this is the number
     * of indices contained in each vector. all vectors must have the
     * same number of indices.
     * @param distance a function that provides the distance between two
     * vectors, recommended that distance returned is normalized
     * @param indexComparator a radiix sorter by vector index
     * @param normalizer provides normalization functionality
     */
    public Crowd(int vectorLength, IProvideDistance<VEC> distance,
            IIndexComparator<VEC> indexComparator, INormalize<VEC> normalizer)
    {
        this.vectorLength = vectorLength;
        this.distance = distance;
        this.indexComparator = indexComparator;
        this.normalizer = normalizer;
    }

    public void increment(VEC vector)
    {
        dirty = true;
        vecs2CD.put(vector, Double.NaN);
    }

    /**
     * Returns a read-only copy of all the vectors considered in this crowd.
     * @return
     */
    public Collection<VEC> getVectors()
    {
        return new HashSet<VEC>(vecs2CD.keySet());
//        return Collections.unmodifiableSet(vecs2CD.keySet());
    }

    public double getCrowdingDistance(VEC vector)
    {
        if (dirty)
        {
            calcCrowdingDistances();
        }
        return vecs2CD.get(vector);
    }

    private void calcCrowdingDistances()
    {
        if (vecs2CD.isEmpty())
        {
            return;
        }
        else if (vecs2CD.size() == 1)
        {
            vecs2CD.put(vecs2CD.keySet().iterator().next(),
                        Double.POSITIVE_INFINITY);
            return;
        }

        final List<VEC> vectors;
        if (normalizer == null)
        {
            vectors = new ArrayList<VEC>(vecs2CD.keySet());
        }
        else
        {
            vectors = new ArrayList<VEC>(vecs2CD.size());
            normalizer.calculateNormalizationFactors(vecs2CD.keySet());
            for (VEC vector : vecs2CD.keySet())
            {
                vectors.add(normalizer.normalize(vector));
            }
        }
        vecs2CD.clear();

        // This portion of the method assumes that we have at least 2 vectors
        for (int i = 0; i < vectorLength; i++)
        {
            indexComparator.setIndex(i);
            Collections.sort(vectors, indexComparator);
            final VEC first = vectors.get(0);
            final VEC second = vectors.get(1);
            final VEC nextToLast = vectors.get(vectors.size() - 2);
            final VEC last = vectors.get(vectors.size() - 1);

            //Lets handle the border individuals first, the greatest & least
            final double greatest = distance.distance(first, second, i);
            //multiple the crowding distance of the greatest by 2, since he
            //has no neighbor to his left, add to prev crowding distance if exists
            if (i == 0)
            {
                //first put, no need to increment in the map
                assert (!vecs2CD.containsKey(first));
                vecs2CD.put(first, 2 * greatest);
            }
            else
            {
                //subsequent put, gotta increment based off prev val in the map
                assert (vecs2CD.containsKey(first));
                vecs2CD.put(first, 2 * greatest + vecs2CD.get(first));
            }

            final double least = distance.distance(last, nextToLast, i);
            if (i == 0)
            {
                assert (!vecs2CD.containsKey(last));
                vecs2CD.put(last, 2 * least);
            }
            else
            {
                assert (vecs2CD.containsKey(last));
                vecs2CD.put(last, 2 * least + vecs2CD.get(last));
            }

            //now lets handle the "regular" middle group
            for (int v = 1; v < vectors.size() - 1; v++)
            {
                final VEC prev = vectors.get(v - 1);
                final VEC cur = vectors.get(v);
                final VEC next = vectors.get(v + 1);
                final double crowdingDistance = distance.distance(prev, cur, i) +
                        distance.distance(cur, next, i);

                if (i == 0)
                {
                    assert (!vecs2CD.containsKey(cur));
                    vecs2CD.put(cur, crowdingDistance);
                }
                else
                {
                    assert (vecs2CD.containsKey(cur));
                    vecs2CD.put(cur, crowdingDistance + vecs2CD.get(cur));
                }
            }
        }
    }
}
